import java.util.Comparator;
import java.util.PriorityQueue;

class MedianFinder {
    public PriorityQueue<Integer> left;
    public PriorityQueue<Integer> right;

    public MedianFinder() {
        left = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });
        right = new PriorityQueue<>();
    }

    public void addNum(int num) {
        int m = left.size();
        int n = right.size();
        if(left.isEmpty()){
            left.offer(num);
        }else{
            if(m == n){
                if(num <= left.peek()){
                    left.offer(num);
                }else{
                    right.offer(num);
                    left.offer(right.poll());
                }
            }else if(m > n){
                if(num <= left.peek()){
                    left.offer(num);
                    right.offer(left.poll());
                }else{
                    right.offer(num);
                }
            }
        }
    }

    public double findMedian() {
        double median = 0;
        int m = left.size();
        int n = right.size();
        if(m == n){
            median += left.peek();
            median += right.peek();
            median /= 2.0;
        }else{
            median += left.peek();
        }
        return median;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */